from typing import List


class Solution:
    def __init__(self):
        self.res = []
        self.letter_map = {2: "abc", 3: "def", 4: "ghi", 5: "jkl",
                           6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}

    def find(self, digits: str, index: int, s):
        if (index == len(digits)):
            self.res.append(s)
            return
        c = digits[index]
        letters = self.letter_map[int(c)]
        for i in range(len(letters)):
            print("s=", s, "letters[{}]=".format(i), letters[i])
            self.find(digits, index+1, s + letters[i])

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        self.find(digits, 0, "")
        return self.res


print(Solution().letterCombinations("234"))
